# 长度最小的子数组：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

# 正常逻辑
class Solution:
    def minSubArrayLen(self, s: int, nums: list) -> int:
        """
            使用滑动窗口解题: 其实也有细节要考虑。 滑动窗口是闭区间，[i, j] , 考虑闭区间内，这样去想就行了
        """
        total = 0
        i, j, n = 0, 0, len(nums)
        minLength = n + 1 
        # j 代表右边界，滑出界就结束循环
        while j < n: 
            # 因为是闭区间，所以应该先添加进去，此时 i = j = 0， 滑动窗口内该有一个元素[0, 0]，再进行后序判断
            # 保证下面判断，每次判断的都是 [i, j] 闭区间内元素！
            total += nums[j]
            # 小于， 窗口向右扩大
            if total < s:     
                j += 1
            # 大于等于，一直循环从左缩小窗口
            else:
                while total >= s: 
                    minLength = min(minLength, j - i + 1)                
                    total -= nums[i]
                    i += 1
                j += 1

        return minLength if minLength != n + 1 else 0


# 优化后写法
class Solution:
    def minSubArrayLen(self, s: int, nums: list) -> int:
        """
            使用滑动窗口解题: 其实也有细节要考虑。 滑动窗口是闭区间，[i, j] , 这样去想就行了
        """
        total = 0
        i, j, n = 0, 0, len(nums)
        minLength = n + 1 
        while j < n: 
            total += nums[j]

            while total >= s: 
                minLength = min(minLength, j - i + 1)                
                total -= nums[i]
                i += 1
            j += 1

        return minLength if minLength != n + 1 else 0


# 前缀和写法
class Solution:
    def minSubArrayLen(self, s: int, nums: list) -> int:
        """
            因为题目给出 1 <= nums[i] <= 105， 那么可以使用前缀和 加二分查找做
            1. 因为元素都大于0，所以前缀和肯定是递增的
            2. 我们以每一个元素为起始位置，二分找第一个大于 target的重点位置， 比较那个最小
            二分查找一次是 logn,  一共查找n次
            那么时间复杂度为 O(nlogn)
        """
        n = len(nums)
        # 1. 计算前缀和, 初始长度为 n + 1, 方便计算. 任意 长度的和，均等于 prefix[i] - prefix[i - 1]
        prefix = [0] * (n + 1)
        for i in range(0, n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        # 2. 定义二分查找方法
        def binarySreach(nums, start, target):
            """
                1. 这里要理清楚， 假如 nums = 1 2 3 4，  prefix是 0 1 3 6 10 长度是 n + 1.
                2. 依次遍历 nums， start 假如为1， 对应 nums的元素2， 前缀和prefix里对应的是 3， 下标为 2！ 计算nums里 2 + 3 + 4 的和， 对应到 prefix里是 prefix[n] - prefix[1], 所以搜索起来是从 start + 1开始到最后
                3. start对应 nums元素下标，  start + 1 对应的是 prefix中， 此元素的前缀和。
            """
            left = start + 1
            # 这里的nums 是 prefix
            right = len(nums) - 1
            while left < right:
                middle = (left + right) // 2 
                if nums[middle] - nums[start] >= target:
                    right = middle
                else:
                    left = middle + 1
            
            # 看最后一个位置 是否符合，有可能小于
            return left - start if nums[left] - nums[start] >= target else n + 1


        # 3. 寻找满足条件长度最小子数组
        minLength = n + 1
        # 使 nums 前n个元素都作为开始元素， 计算第一个 大于 target的子数组长
        for i in range(n):
            length = binarySreach(prefix, i, s)
            minLength = min(minLength, length)
        
        return minLength if minLength != n + 1 else 0


nums = [2,3,1,2,4,3]
target = 7

s = Solution()
rst = s.minSubArrayLen(target, nums)
print(rst)
